package com.wk.data;

import java.util.ArrayList;
import java.util.List;

/**
 * 稀疏数组，存储有用值，棋盘的存档与恢复
 */
public class SparseArray {
    public static void main(String[] args){
        int chessArr[][] = new int[11][11];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        printChess(chessArr);
        int[][] sparseArr = arr2sparse(chessArr);
        printChess(sparseArr);
        int newChess[][] = sparse2arr(sparseArr);
        printChess(newChess);
    }

    /**
     * 稀疏数组转为原始数组
     * @param sparseArr
     * @return
     */
    private static int[][] sparse2arr(int[][] sparseArr){
        int rows = sparseArr[0][0];
        int cols = sparseArr[0][1];
        int sum = sparseArr[0][2];
        int chessArr[][] = new int[rows][cols];
        for (int i=1;i<sum+1;i++){
            chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return chessArr;
    }
    /**
     * 原始数组转稀疏数组
     * @param chessArr
     * @return
     */
    private static int[][] arr2sparse(int[][] chessArr) {
        // 有效值个数
        int sum = 0;
        for (int i = 0;i<11;i++){
            for (int j=0;j<11;j++){
                if (chessArr[i][j]!=0){
                    sum++;
                }
            }
        }
        int[][] sparseArr = new int[sum+1][3];
        sparseArr[0][0] = 11;
        sparseArr[0][1] = 11;
        sparseArr[0][2] = sum;
        int row = 1;
        for (int i = 0;i<11;i++){
            for (int j=0;j<11;j++){
                if (chessArr[i][j]!=0){
                    sparseArr[row][0] = i;
                    sparseArr[row][1] = j;
                    sparseArr[row][2] = chessArr[i][j];
                    row++;
                }
            }
        }
        return sparseArr;
    }

    /**
     * 打印
     * @param chessArr
     */
    private static void printChess(int[][] chessArr) {
        for (int[] row:chessArr) {
            for (int item:row) {
                System.out.printf("%d\t",item);
            }
            System.out.println();
        }
    }
}
